<?php
/**
 * User: helloJiu
 * Date: 2021/9/18
 * Time: 17:21
 */

namespace App\Algorithm;

use App\Util\PrintUtil;

class NQueues
{

    private $n;

    // 记录已经摆过的皇后
    private $queues = [];

    private $ways = 0;

    public function placeQueue($n)
    {
        $this->n = $n;
        $this->place(0);
        PrintUtil::println($this->ways);
    }

    private function place($row)
    {
        if ($row == $this->n) {
            $this->ways++;
            $this->show();
            return;
        }

        for ($col = 0; $col < $this->n; $col++) {
            // 判断皇后是否冲突
            if ($this->isValid($row, $col)) {
                $this->queues[$row] = $col;
                $this->place($row + 1);
            }
        }
    }

    /**
     * 判断是否和已有皇后所在行列以及对角冲突
     * @param $row
     * @param $col
     * @return bool
     */
    private function isValid($row, $col)
    {
        for ($queue_row = 0; $queue_row < $row; $queue_row++) {
            // 遍历以后皇后, 判断是否冲突
            // 在同一列
            if ($this->queues[$queue_row] == $col) return false;
            // 在同一斜线
            if (($row - $queue_row) / abs(($col - $this->queues[$queue_row])) == 1) {
                return false;
            }
        }
        return true;
    }

    private function show(){
        for($i=0; $i<$this->n;$i++){
            for($j=0;$j<$this->n;$j++){
                if($this->queues[$i] == $j){
                    PrintUtil::print(1 . '  ');
                }else{
                    PrintUtil::print(0 . '  ');

                }
            }
            PrintUtil::println('');
        }
        PrintUtil::println('--------------');
    }
}